描述

设计一个算法,计算出n阶乘中尾部零的个数

样例

11! = 39916800,因此应该返回 2

挑战

O(logN)的时间复杂度

先看个表

1 阶乘 1 2 阶乘 2 3 阶乘 6 4 阶乘 24 5 阶乘 120 6 阶乘 720 7 阶乘 5040 8 阶乘 40320 9 阶乘 362880 10 阶乘 3628800 11 阶乘 39916800 12 阶乘 479001600 13 阶乘 6227020800 14 阶乘 87178291200 15 阶乘 1307674368000 16 阶乘 20922789888000 17 阶乘 355687428096000 18 阶乘 6402373705728000 19 阶乘 121645100408832000 20 阶乘 2432902008176640000 21 阶乘 51090942171709440000 22 阶乘 1124000727777607680000 23 阶乘 25852016738884976640000 24 阶乘 620448401733239439360000 25 阶乘 15511210043330985984000000 26 阶乘 403291461126605635584000000 27 阶乘 10888869450418352160768000000 28 阶乘 304888344611713860501504000000 29 阶乘 8841761993739701954543616000000 30 阶乘 265252859812191058636308480000000 31 阶乘 8222838654177922817725562880000000 32 阶乘 263130836933693530167218012160000000 33 阶乘 8683317618811886495518194401280000000 34 阶乘 295232799039604140847618609643520000000 35 阶乘 10333147966386144929666651337523200000000 36 阶乘 371993326789901217467999448150835200000000 37 阶乘 13763753091226345046315979581580902400000000 38 阶乘 523022617466601111760007224100074291200000000 39 阶乘 20397882081197443358640281739902897356800000000 40 阶乘 815915283247897734345611269596115894272000000000 41 阶乘 33452526613163807108170062053440751665152000000000 42 阶乘 1405006117752879898543142606244511569936384000000000 43 阶乘 60415263063373835637355132068513997507264512000000000 44 阶乘 2658271574788448768043625811014615890319638528000000000 45 阶乘 119622220865480194561963161495657715064383733760000000000 46 阶乘 5502622159812088949850305428800254892961651752960000000000 47 阶乘 258623241511168180642964355153611979969197632389120000000000 48 阶乘 12413915592536072670862289047373375038521486354677760000000000 49 阶乘 608281864034267560872252163321295376887552831379210240000000000 50 阶乘 30414093201713378043612608166064768844377641568960512000000000000

首先末尾的0和末尾的2和5有关系,以及其倍数. 2的倍数远远多于5的倍数,那么,计算总共几个5即可. 例如16! 16//5=3 一共是3个5,那么结果呢 16 阶乘 20922789888000 果然如此!同理的话,32! 32//5=6 那么就是6个0了吗? 32 阶乘 263130836933693530167218012160000000 咦?有7个0,好像有哪里不对? 32里面有个特殊的值是25,25=5*5,多了一个5! 那么,那么下一个多5的地方也就是25*2=50,所以一直除5到不足1为止 刚刚的例子32! 32//5=6  ;  6//5=1  ;  6+1=7 继续下一个例子50! 50//5=10  ;  10//5=2  ;  10+2 50 阶乘 30414093201713378043612608166064768844377641568960512000000000000 那么正确了 py3代码

class Solution: def trailingZeros(self, n): # write your code here, try to do it without arithmetic operators. sum=0 while n>int1: n=int(n/5) sum+=n return sum